
//Q3.整理书架
class Solution {
public:
    vector<int> arrangeBookshelf(vector<int>& nums, int limit) {
        int n=nums.size();
        unordered_map<int,int> m; //统计数组中各个数组出现的次数
        for(auto e:nums) m[e]++;

        //使用单调栈
        vector<int> ret; 
        unordered_map<int,int> have;  //存储数组中已经存在的数字及个数
        for(int i=0;i<n;i++)
        {
            if(have.count(nums[i])&&have[nums[i]]==limit)
            {
                m[nums[i]]--;
                 continue;
            }                                  //have[ret.back()]+m[ret.back()]>limit保证后面的个数和已经存在的个数>limit才能出 
            while(!ret.empty()&&ret.back()>nums[i]&&m[ret.back()]&&have[ret.back()]+m[ret.back()]>limit) 
            {
                have[ret.back()]--;
                ret.pop_back();
            }

            have[nums[i]]++;
            ret.push_back(nums[i]);
            m[nums[i]]--;
        }
        return ret;
    }
};